class Solution {
    int cnt = 0;

    // 归并排序
    public int reversePairs(int[] nums) {

        mergeSort(nums, 0, nums.length - 1);
        return cnt;
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;

        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, right, mid);
    }

    private void merge(int[] nums, int left, int right, int mid) {
        int[] tmp = new int[right - left + 1];
        // 开始合并
        int i = left; // 定义i指针指向第一个数组第一个字符
        int j = mid + 1;// 定义j指针指向第二个数组第一个字符
        int pos = 0; // 定义pos指针指向临时数组
        // 排序好的都放到临时数组中
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                tmp[pos++] = num[i++];
            else {
                tmp[pos++] = nums[j++];
                cnt += mid - i + 1; // 合并时，当左边大于右边，计算逆序数
            }
        }
        while (i <= mid)
            tmp[pos++] = nums[i++];
        while (j <= right)
            tmp[pos++] = nums[j++];

        for (int k = 0; k < (right - left + 1); ++k)
            nums[left + k] = tmp[k];
    }

    // 会超时
    public int reversePairs1(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) {
                    sum++;
                }
            }

        }
        return sum;
    }
}